package everyday;

/**
 * @author ZhanBo
 * @date 2020/7/27
 */
public class Solution392 {

    public static void main(String[] args) {
        String s ="";
        String t = "aecde";
        System.out.println(isSubsequence(s, t));
    }

    public static boolean isSubsequence(String s, String t) {
        int index = 0;
        if ((s==null&&t==null) || (s.length()==0)){
            return true;
        }
        if (s.equals(t)){
            return true;
        }
        for (int i = 0 ; i < t.length() ; i++){
            if (t.charAt(i) == s.charAt(index)){
                index++;
            }
            if (index == s.length()){
                break;
            }
        }
        return index == s.length();
    }

    /**
     * 双指针
     * 这样，我们初始化两个指针 ii 和 jj，分别指向 ss 和 tt 的初始位置。每次贪心地匹配，
     * 匹配成功则 ii 和 jj 同时右移，匹配 ss 的下一个位置，匹配失败则 jj 右移，ii 不变，尝试用 tt 的下一个字符匹配 ss。
     *
     * 最终如果 ii 移动到 ss 的末尾，就说明 ss 是 tt 的子序列。
     *
     * @param s
     * @param t
     * @return
     */
    public static boolean isSubsequence2(String s, String t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == n;
    }

}
